package basic.sort.hash;

import java.util.HashMap;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.hash
 * @since JDK1.8
 *
 * 设计一种结构，在该结构中实现三个功能
 * insert(key):将某个key加入到该结构，做到不重复加入
 * delete(key):将原本在结构中的某个key移除
 * getRandom ():等概率随机返回结构中的任何一个key。
 */
public class RandomPool {
    private static HashMap<String, Integer> mapStrToInt = new HashMap<>();
    private static HashMap<Integer, String> mapIntToStr = new HashMap<>();
    private static int size = 0;

    /**
     * 将某个key加入到该结构，做到不重复加入
     * @param key 想要插入的key
     */
    private static void insert(String key) {
        if (!mapStrToInt.containsKey(key)) {
            mapStrToInt.put(key, size);
            mapIntToStr.put(size++, key);
        }
    }

    private static void delete(String key) {
        if (mapStrToInt.containsKey(key)) {
            int lastIndex = --size;
            String lastKey = mapIntToStr.get(lastIndex);
            int deleteIndex = mapStrToInt.get(key);
            mapStrToInt.put(lastKey, deleteIndex);
            mapIntToStr.put(deleteIndex, lastKey);
            mapStrToInt.remove(key);
            mapIntToStr.remove(size--);
        }
    }

    private static String getRandom() {
        if (size == 0) {
            return null;
        }

        int random = (int) (Math.random() * size);
        return mapIntToStr.get(random);
    }
}
